package leetcode.code0382;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.HelpDebug;
import leetcode.helper.tree.ListNode;

//执行用时：10 ms, 在所有 Java 提交中击败了97.32%的用户
//
//内存消耗：40.3 MB, 在所有 Java 提交中击败了60.60%的用户
//
//通过测试用例：8 / 8
public class Solution2 {

	List<Integer> list;
	int size;

	public Solution2(ListNode head) {
		list = new ArrayList<>();
		size = 0;
		while (head != null) {
			list.add(head.val);
			head = head.next;
			size++;
		}
	}

	public int getRandom() {
		return list.get((int) (Math.random() * size));
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2(ListNode.set(HelpDebug.str2array3("[1,2,3,4,5,6]")));
		for (int i = 0; i < 20; i++) {
			System.out.println(so.getRandom());
		}
	}

}
